深色模式
3184. 构成整天的下标对数目 I
题目描述
题目链接: 3184. 构成整天的下标对数目 I
给你一个整数数组 hours，表示以 小时 为单位的时间，返回一个整数，表示满足 i < j 且 hours[i] + hours[j] 构成 整天 的下标对 i, j 的数目。
整天 定义为时间持续时间是 24 小时的 整数倍 。
示例 1：
输入： hours = [12,12,30,24,24]
输出： 2
解释：
构成整天的下标对分别是 (0, 1) 和 (3, 4)。示例 2：
输入： hours = [72,48,24,3]
输出： 3
解释：
构成整天的下标对分别是 (0, 1)、(0, 2) 和 (1, 2)。题解
方法一：暴力枚举
遍历数组，找到整除24的一对数
py
class Solution:
def countCompleteDayPairs(self, hours):
length = len(hours)
count = 0
for i in range(length):
for j in range(i+1, length):
if (hours[i] + hours[j]) % 24 == 0:
count += 1
return count分析：
时间复杂度:
空间复杂度:
方法二：哈希表分析
LeetCode 上面有很多人贴出了使用 hash 进行排列组合算法， 现在将其贴出来
py
class Solution:
def countCompleteDayPairs(self, hours: List[int]) -> int:
ans = 0
cnt = [0] * 24
for hour in hours:
ans += cnt[(24 - hour % 24) % 24]
# 注意这里在还没有循环结束结加一次，下一次遇到相同又加了一次，为什么呢？
# 因为本次出现一个数，与只对应形成了组合
# 下一次出现数，位子变了，形成下一次的组合，又加了一次
# 比如 cn[8] = 3, cn[16] =2, 则本次8出现時，需要组合 (8,16) 两次，此时16表示两次不同位子
cnt[hour % 24] += 1
return ans
作者：力扣官方题解
链接：https://leetcode.cn/problems/count-pairs-that-form-a-complete-day-ii/solutions/2928185/gou-cheng-zheng-tian-de-xia-biao-dui-shu-4ijs/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。